public class countSeqments {

    // 记录状态
    enum Side {LEFT, FARMER, FOX, DUCK, CORN, RIGHT}

    static class State {
        public Side item;
        Side farmer;
        Side fox;
        Side duck;
        Side corn;

        State(Side farmer, Side fox, Side duck, Side corn) {
            this.farmer = farmer;
            this.fox = fox;
            this.duck = duck;
            this.corn = corn;
        }

        // 打印状态
        @Override
        public String toString() {
            return "Farmer: " + farmer + ", Fox: " + fox + ", Duck: " + duck + ", Corn: " + corn;
        }

        // 判断是否有效状态
        boolean isValid() {
            return !((fox == duck && fox != farmer) || (duck == corn && duck != farmer));
        }

        // 判断是否是目标状态
        boolean isGoal() {
            return farmer == Side.RIGHT && fox == Side.RIGHT && duck == Side.RIGHT && corn == Side.RIGHT;
        }
    }

    public static void main(String[] args) {
        State initialState = new State(Side.LEFT, Side.LEFT, Side.LEFT, Side.LEFT);
        solve(initialState);
    }

    private static void solve(State state) {
        if (state.isGoal()) {
            System.out.println("Goal Reached: " + state);
            return;
        }

        if (!state.isValid()) {
            return;
        }

        // 进行每一步尝试
        Side[] items = {Side.FARMER, Side.FOX, Side.DUCK, Side.CORN};
        for (Side item : items) {
            State newState = move(state, item);
            if (newState != null) {
                System.out.println(newState);
                solve(newState);
            }
        }
    }

    private static State move(State state, Side item) {
        // 移动农夫和物品
        if (item == Side.FARMER) {
            return new State(
                    flip(state.farmer),
                    state.fox,
                    state.duck,
                    state.corn
            );
        }

        // 农夫与其他物品一起过河
        if (state.farmer == state.item) {
            return new State(
                    flip(state.farmer),
                    item == Side.FOX ? flip(state.fox) : state.fox,
                    item == Side.DUCK ? flip(state.duck) : state.duck,
                    item == Side.CORN ? flip(state.corn) : state.corn
            );
        }

        return null;
    }

    private static Side flip(Side side) {
        return side == Side.LEFT ? Side.RIGHT : Side.LEFT;
    }
}
